package Queue;

import java.util.LinkedList;
import java.util.Queue;

/**
 *  题目 ：滑动窗口的平均值
 *  题目详述 ：
 *  给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
 * 实现 MovingAverage 类：
 * MovingAverage(int size) 用窗口大小 size 初始化对象。
 * double next(int val)成员函数 next每次调用的时候都会往滑动窗口增加一个整数，
 * 请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
 */
public class MovingAverage {
    /**
     * 核心思想 ：
     * 即，使用队列来表示滑动窗口；
     * 当滑动窗口达到容量上限后，会去删除其中最先插入的元素，同时在滑动窗口的末端插入新元素
     * @param size
     */

    private Queue<Integer> queue; // 使用队列数据结构，来表示滑动窗口；
    private Integer sum; // 计算滑动窗口的总值；
    private Integer capacity; // 初始化时获取滑动窗口的大小；

    public MovingAverage(int size) {
        queue = new LinkedList<>(); // 对于队列进行初始化
        capacity = size; // 初始化获取滑动窗口的大小
        sum = 0;
    }

    public double next(int val) {
        queue.offer(val); // 向队列中插入元素
        sum += val; // sum永远都会加上新插入的元素；
        if (queue.size() > capacity){
            // 即，队列的大小和滑动窗口的大小一致，即queue.size == capacity
            Integer poll = queue.poll();
            sum -= poll; // sum（总值），需要减去从队列中移除的元素
        }
        // 此处不能直接将 queue.size == capacity 直接等价；
        // 特殊情况 : 即，队列未满（未达到滑动窗口的最大容量），不能够直接使用总值/滑动窗口的最大容量
        return sum * 1.0 / queue.size();
    }
    /**
     *  分析 ：
     *  （1）时间复杂度 ：
     *      即,由于MovingAverage方法（初始化），next方法都没有循环的出现
     *      ===》 O（1）
     *  （2）空间复杂度 ：
     *      即，由于空间消耗主要在于队列的建立；同时队列的长度又是依赖于滑动窗口的大小
     *      ===> O（size）（即，滑动窗口的大小）
     */
}
